package LeetCode;
/**
 * leetcode203.给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回 新的头节点
 */
public class Num203 {
    public static void main(String[] args) {

    }
    ListNode head;
    public static ListNode build(){
        ListNode node1=new ListNode(1);
        ListNode node2=new ListNode(2);
        ListNode node3=new ListNode(3);
        ListNode node4=new ListNode(4);
        ListNode node5=new ListNode(5);
        ListNode node6=new ListNode(6);
        node1.next=node2;
        node2.next=node3;
        node3.next=node4;
        node4.next=node5;
        node5.next=node6;
        return node1;
    }
    /**
     * 删除链表中所有值为val的节点
     * @param head 头节点
     * @param val 删除的值
     * @return 返回新的头节点
     */
    public ListNode removeElements(ListNode head, int val) {
        //3.虚拟头节点-这个节点不存储具体值，只作为链表的头部-此时插入元素节点都可以看作中间节点。前驱prev遍历从虚拟头节点处开始
        ListNode dummyHead = new ListNode(-1);
        dummyHead.next=head;
        ListNode prev = dummyHead;
        while (prev.next != null) {
            if (prev.next.val == val) {
                ListNode cur = prev.next;
                prev.next = cur.next;
            } else {
                prev = prev.next;
            }
        }
        return dummyHead.next;
        //2.递归
        //已知头节点head和val值。出口，拆到最后一个节点就没了
//       if(head==null){
//           return null;
//       }
//       head.next=removeElements(head.next,val);
//       //自己再处理一下节点
//       if(head.val==val){
//           return head.next;
//       }else{
//           return head;
//       }
        //1.未使用虚拟头节点的解法
//        while(head!=null&&head.val==val){
//            //头结点是待删除节点
//            head=head.next;
//        }
//        if(head==null){
//            return null;
//        }else{//头节点一定不是待删除结点
//            ListNode prev=head;
//            while(prev.next!=null){
//                if(prev.next.val==val){
//                    //说明prev.next是待删除结点
//                    ListNode cur=prev.next;
//                    prev.next=cur.next;
//                    cur.next=null;
//                }else{
//                    prev=prev.next;
//                }
//            }
//        }
//        return head;
    }

}
 class ListNode {
    int val;
    ListNode next;

    ListNode() {
    }

    ListNode(int val) {
        this.val = val;
    }

    ListNode(int val, ListNode next) {
        this.val = val;
        this.next = next;
    }
}